//
// Created by WANGYX on 2021/6/4.
//

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
void binarySort(vector<T> &list)     // 折半插入排序
{
    int length = list.size();
    for(auto i=1; i<length; i++)
    {
        T temp = list[i];
        auto low = 0;
        auto high = i-1;
        while(low <= high)
        {
            auto mid = (low+high)/2;
            if(temp < list[mid])    // 前移
                high = mid-1;
            else                    // 后移
                low = mid+1;
        }
        for(auto j=i-1; j>=low; j--)
            list[j+1] = list[j];    // 向后移动腾出位置
        list[low] = temp;
    }
}

template<typename T>
void bubbleSort(vector<T> &list)      // 改进的冒泡排序算法
{
    int length = list.size();
    bool flag = true;
    for(auto i=1; i<length && flag; i++)
    {
        flag = false;
        for(auto j=0; j<length-i; j++)
        {
            if(list[j] > list[j+1])
            {
                T temp = std::move(list[j]);       // 交换元素位置
                list[j] = std::move(list[j+1]);
                list[j+1] = std::move(temp);
                flag = true;
            }
        }
    }
}

template<class T>
void quickSort(vector<T> &list, int l, int r)	// 子集划分过程
{
    T temp;
    int pos = 0;
    int low = l;
    int high = r;
    if(l < r)
    {
        temp = list[l];
        while(low < high)
        {
            while((low < high) && (list[high] >= temp))
            {
                high--;
            }
            if(low < high)
            {
                list[low] = list[high];
                low++;
            }
            while((low < high) && (list[low] < temp))
            {
                low++;
            }
            if(low < high)
            {
                list[high] = list[low];
                high--;
            }
        }
        list[low] = temp;
        pos=low;
        quickSort(list, l, pos-1);
        quickSort(list, pos+1, r);
    }
}

template<typename T>
void selectSort(vector<T> &list)     // 简单选择排序
{
    int length = list.size();
    for(auto i=0; i<length-1; i++)
    {
        int k=i;    // 在n-i个记录中选取关键字最小的记录作为有序序列中第i个记录。
        for(auto j=i+1; j<length; j++)
        {
            if(list[j] < list[k])
                k=j;
        }
        if(k!=i)
        {
            T temp = std::move(list[i]);    // 交换元素位置
            list[i] = std::move(list[k]);
            list[k] = std::move(temp);
        }
    }
}

template<typename T>
void mergeSort(vector<T> &res, int low, int high, vector<T> &list)       // 归并排序
{
    if(low < high)
    {
        int mid=(low+high)/2;
        mergeSort(res,low,mid,list);      // 本质是将待排序列中相邻的两个有序子序列合并成一个有序序列
        mergeSort(res,mid+1,high,list);
        int i = low;
        int j = mid+1;
        int k = low;
        while((i <= mid) && (j <= high))
        {
            if(res[i] <= res[j])
            {
                list[k] = res[i];
                i++;
            }
            else
            {
                list[k] = res[j];
                j++;
            }
            k++;
        }

        while(i <= mid)
        {
            list[k] = res[i];
            k++;
            i++;
        }

        while(j <= high)
        {
            list[k] = res[j];
            k++;
            j++;
        }

        for(auto index=low; index<=high; index++)
            res[index] = list[index];
    }
}

template<typename T>
void percDown(vector<T> &list, int p, int n)     // 将N个元素的数组中以A[p]为根的子堆调整为最大堆
{
    int Parent, Child;
    T temp;
    if(p < 0 || p > n-1)
        return;
    temp = list[p];     // 取出根结点存放的值
    for(Parent = p; (Parent*2+1) < n; Parent = Child)
    {
        Child = Parent*2 + 1;
        if(Child < n-1 && (list[Child] < list[Child+1]) )     // 使Child指向左右子结点的较大者
            Child++;
        if(temp >= list[Child])      // 找到了合适位置
            break;
        else
            list[Parent] = list[Child];   // 下滤temp
    }
    list[Parent] = temp;
}

template<typename T>
void heapSort(vector<T> &list)     // 堆排序
{
    int length = list.size();
    for(auto i = length/2-1; i>=0; i--)     // 建立最大堆
        percDown(list, i, length);
    for(auto i = length-1; i>0; i--)        // 删除最大堆顶
    {
        T temp = std::move(list[0]);    // 交换元素位置
        list[0] = std::move(list[i]);
        list[i] = std::move(temp);
        percDown(list, 0, i);
    }
}

